package me.chan.unionfind;

/**
 * 并查集
 * Created by JanGin on 2020/4/27.
 */
public class UnionFind {

    private int[] roots;

    public UnionFind(int N) {
        roots = new int[N];
        for (int i = 0; i < N; ++i) {
            roots[i] = i;   //初始化
        }
    }

    private int findRoot(int i) {
        int root = i;        //根节点
        while (roots[root] != i) {
            root = roots[root];
        }
        //在查找的过程中进行路径压缩
        while (i != roots[i]) {
            int tmp = roots[i];
            roots[i] = root;
            i = tmp;
        }

        return root;
    }

    /**
     * 判断两个元素是否存在于同一集合
     * @param p
     * @param q
     * @return
     */
    public boolean isConnected(int p, int q) {
        return findRoot(p) == findRoot(q);
    }

    /**
     * 合并两个元素所在的子集合
     * @param p
     * @param q
     */
    public void union(int p, int q) {
        int proot = findRoot(p);
        int qroot = findRoot(q);
        roots[proot] = qroot;
    }
}
